/**
 * 1262.可被三整除的最大和
 */
public class Exerciser7 {
    /**
     * 动态规划通用
     * @param nums
     * @return
     */
    public int maxSumDivThree1(int[] nums) {
        int len = nums.length;
        int[][] dp = new int[len+1][3];//前i个nums能构成余数为j的最大值
        dp[0][1]=dp[0][2]=Integer.MIN_VALUE;
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < 3; j++) {
                dp[i][j]=Math.max(dp[i-1][j],dp[i-1][(j+nums[i-1])%3]+nums[i-1]);
            }
        }
        return dp[len][0];
    }

    /**
     * 贪心算法
     * @param nums
     * @return
     */
    public int maxSumDivThree(int[] nums) {
        // 正难则反
        // 先把所有的数进行加法求和之后 ，假设 x 为 %3==1的 ，y 为 %3 == 2的
        // 把sum%3 == 0 则直接返回
        // sum % 3 == 1 说明存在一个 x(最小的) 或者 两个y，一个是最小的一个是次小的
        // sum % 3 == 2 说明存在一个 y(最小的) 或者 两个x，一个是最小的一个是次小的
        int INF = 0x3f3f3f3f;
        int sum = 0;
        // x1 是 %3==1 中最小的，x2 是 %3==1 中次小的
        // y1 是 %3==2 中最小的，y2 是 %3==2 中次小的
        int x1 = INF,x2 = INF;
        int y1 = INF,y2 = INF;
        for(int x : nums) {
            sum += x;
            if(x % 3 == 1) {
                if(x < x1) {
                    x2 = x1;
                    x1 = x;
                }else if(x < x2) {
                    x2 = x;
                }
            }else if(x % 3 == 2) {
                if(x < y1) {
                    y2 = y1;
                    y1 = x;
                }else if(x < y2) {
                    y2 = x;
                }
            }
        }

        // 分情况讨论
        if(sum % 3 == 0) {
            return sum;
        }else if(sum % 3 == 1) {
            return Math.max(sum - x1,sum - y1 - y2);
        }else if(sum % 3 == 2) {
            return Math.max(sum - x1 - x2,sum - y1);
        }
        return 0;
    }
}
